/*
 * Fibonacci.java
 *
 * Created on December 16, 2001, 1:20 AM
 *
 * Copyright 2008 the Desert Labs Project (http://desertlabs.us)
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package us.desertlabs.number;

import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 * This class allows the dynamic generation of individual numbers within the
 * Fibonacci series. It can be used just like any other <CODE>Number</CODE> in
 * Java, which makes it very convenient for mathematical operations and for
 * storage in collections.
 * <P>
 * Internally, the <CODE>Fibonacci</CODE> class uses a math trick to calculate
 * values in the series up to position 70. Beyond that, the values begin to be
 * corrupted by internal rounding errors, and the algorithm must switch to using
 * a brute-force calculation method.
 * <P>
 * The class is capable of generating and storing any Fibonacci number whose
 * position in the series can be described using a 64-bit <CODE>long</CODE>.
 * <P>
 * Also of note, this class can be used as a source of the constant Phi, since
 * it is a calculated public field of the <CODE>Fibonacci</CODE> class.
 *
 * @author Brandon Franklin
 */
public final class Fibonacci extends Number implements Comparable<Number>, Cloneable {

    /** An approximation of the "phi" constant (P = 1.618033988749895) */
    final static public transient double PHI = (Math.sqrt( 5.0 ) / 2) + 0.5;

    /** A precalculated table of some of the lowest Fibonacci numbers */
    final static private transient int[] LOOKUP_TABLE = new int[]{
        0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610
    };

    final static private long serialVersionUID = 3258413915309158705L;

    /**
     * Returns the Fibonacci number at the specified position in the series. The
     * number will be calculated using a combination of the math trick and brute
     * force addition.
     *
     * @param position the position of the number within the Fibonacci series
     * @return the Fibonacci number at the specified position in the series
     */
    private static Number getUsingBruteForce( final long position ) {

        BigInteger bigInt1 = new BigInteger( new Fibonacci( 69 ).toString() );
        BigInteger bigInt2 = new BigInteger( new Fibonacci( 70 ).toString() );
        BigInteger temp = null;

        long decPos = position;
        while( decPos > 70 ) {
            temp = bigInt2.add( bigInt1 );
            bigInt1 = bigInt2;
            bigInt2 = temp;

            decPos--;
        }

        return bigInt2;
    }

    /**
     * Returns the Fibonacci number at the specified position in the series. The
     * number will be obtained from the precalculated lookup table.
     *
     * @param position the position of the number within the Fibonacci series
     * @return the Fibonacci number at the specified position in the series
     */
    private static Number getUsingLookupTable( final int position ) {
        if( position >= LOOKUP_TABLE.length ) {
            throw new IllegalArgumentException( "The requested position is too high for the lookup table." );
        }

        return LOOKUP_TABLE[position];
    }

    /**
     * Returns the Fibonacci number at the specified position in the series. The
     * number will be calculated using a math trick.
     *
     * @param position the position of the number within the Fibonacci series
     * @return the Fibonacci number at the specified position in the series
     */
    private static Number getUsingMathTrick( final long position ) {
        final double estimate = Math.pow( PHI, position ) / Math.sqrt( 5.0 );
        return Math.round( estimate );
    }

    /** The position of this number in the Fibonacci series */
    final private long position;

    /** The value of this Fibonacci number */
    final private Number value;

    /**
     * Creates a Fibonacci number with the value "0".
     */
    public Fibonacci() {
        this( 0 );
    }

    /**
     * Creates the Fibonacci number at the specified position within the
     * Fibonacci series.
     *
     * @param position the position of the number within the Fibonacci series
     */
    public Fibonacci( final long position ) {

        this.position = position;

        if( position < LOOKUP_TABLE.length ) { // We can use the lookup table
            value = getUsingLookupTable( (int)position );

        } else if( position <= 70 ) { // We can use a trick
            value = getUsingMathTrick( position );

        } else { // We'll have to brute force it some
            value = getUsingBruteForce( position );
        }

    }

    /**
     * Builds and returns a clone of this object.
     *
     * @return a clone of this object
     */
    @Override
    public Object clone() {
        Fibonacci clone = null;
        try {
            clone = (Fibonacci)super.clone();
        } catch( final CloneNotSupportedException cnse ) {
            Logger.getLogger( getClass().getName() ).log( Level.SEVERE, "Unable to clone Fibonacci object.", cnse );
        }

        return clone;
    }

    /**
     * Compares this <CODE>Fibonacci</CODE> with the specified <CODE>Object</CODE>.
     * If the <CODE>Object</CODE> is a <CODE>Fibonacci</CODE>, this method
     * examines the positions of the two numbers within the Fibonacci series,
     * and returns a result based on that (since numbers higher in the series
     * will always have greater value, excluding the initial pair of 1's).
     * <P>
     * If the <CODE>Object</CODE> is another type of <CODE>Number</CODE>,
     * the actual numerical values will be compared.
     *
     * @param obj <CODE>Object</CODE> to which this <CODE>Fibonacci</CODE>
     *        is to be compared
     * @return a negative number, zero, or a positive number as this <CODE>Fibonacci</CODE>
     *         is numerically less than, equal to, or greater than <CODE>obj</CODE>
     * @see Comparable
     */
    @Override
    public int compareTo( final Number obj ) {
        if( obj instanceof Fibonacci ) {
            final Long myPos = getPosition();
            final Long itsPos = ((Fibonacci)obj).getPosition();
            return myPos.compareTo( itsPos );
        }

        final BigDecimal objDec = new BigDecimal( obj.toString() );
        final BigDecimal valueDec = new BigDecimal( getValue().toString() );
        return valueDec.compareTo( objDec );
    }

    /**
     * Converts this <CODE>Fibonacci</CODE> to a <CODE>double</CODE>.
     * Similar to the double-to-float <i>narrowing primitive conversion</i>
     * defined in <i>The Java Language Specification</i>: if this <CODE>Fibonacci</CODE>
     * has too great a magnitude to represent as a <CODE>double</CODE>, it
     * will be converted to infinity or negative infinity, as appropriate.
     *
     * @return this <CODE>Fibonacci</CODE> converted to a <CODE>double</CODE>
     */
    @Override
    public double doubleValue() {
        return value.doubleValue();
    }

    /**
     * Compares this <CODE>Fibonacci</CODE> with the specified <CODE>Object</CODE>
     * for equality.
     *
     * @param obj <CODE>Object</CODE> to which this <CODE>Fibonacci</CODE>
     *        is to be compared
     * @return <CODE>true</CODE> if and only if the specified <CODE>Object</CODE>
     *         is a <CODE>Fibonacci</CODE> or <CODE>Number</CODE> whose
     *         value is numerically equal to this <CODE>Fibonacci</CODE>
     */
    @Override
    public boolean equals( final Object obj ) {
        if( obj == this ) {
            return true;

        } else if( obj instanceof Fibonacci ) {
            return (((Fibonacci)obj).getPosition() == getPosition());

        } else if( obj instanceof Number ) {
            final BigDecimal objDec = new BigDecimal( ((Number)obj).toString() );
            final BigDecimal valueDec = new BigDecimal( getValue().toString() );
            return valueDec.equals( objDec );

        } else {
            return false;
        }
    }

    /**
     * Converts this <CODE>Fibonacci</CODE> to a <CODE>float</CODE>.
     * Similar to the double-to-float <i>narrowing primitive conversion</i>
     * defined in <i>The Java Language Specification</i>: if this <CODE>Fibonacci</CODE>
     * has too great a magnitude to represent as a <CODE>float</CODE>, it
     * will be converted to infinity or negative infinity, as appropriate.
     *
     * @return this <CODE>Fibonacci</CODE> converted to a <CODE>float</CODE>
     */
    @Override
    public float floatValue() {
        return value.floatValue();
    }

    /**
     * Returns the position of this number within the Fibonacci series.
     *
     * @return the position of this number within the Fibonacci series
     */
    public long getPosition() {
        return position;
    }

    /**
     * Returns the value of this <CODE>Fibonacci</CODE>.
     *
     * @return the value of this <CODE>Fibonacci</CODE>
     */
    public Number getValue() {
        return value;
    }

    /**
     * Returns the hash value for this <CODE>Fibonacci</CODE>, which will be
     * generated based on its numerical value, using the algorithm supplied by
     * the value <CODE>Number</CODE> object's implementation.
     *
     * @return the hash value for this <CODE>Fibonacci</CODE>
     */
    @Override
    public int hashCode() {
        return value.hashCode();
    }

    /**
     * Converts this <CODE>Fibonacci</CODE> to an <CODE>int</CODE>.
     * Standard <i>narrowing primitive conversion</i> as defined in <i>The Java
     * Language Specification</i>: if this <CODE>Fibonacci</CODE> is too big
     * to fit in an <CODE>int</CODE>, only the low-order 32 bits are
     * returned.
     *
     * @return this <CODE>Fibonacci</CODE> converted to an <CODE>int</CODE>
     */
    @Override
    public int intValue() {
        return value.intValue();
    }

    /**
     * Converts this <CODE>Fibonacci</CODE> to a <CODE>long</CODE>.
     * Standard <i>narrowing primitive conversion</i> as defined in <i>The Java
     * Language Specification</i>: if this <CODE>Fibonacci</CODE> is too big
     * to fit in a <CODE>long</CODE>, only the low-order 64 bits are
     * returned.
     *
     * @return this <CODE>Fibonacci</CODE> converted to a <CODE>long</CODE>
     */
    @Override
    public long longValue() {
        return value.longValue();
    }

    /**
     * Returns the <CODE>String</CODE> representation of this <CODE>Fibonacci</CODE>.
     *
     * @return the <CODE>String</CODE> representation of this <CODE>Fibonacci</CODE>
     */
    @Override
    public String toString() {
        return value.toString();
    }
}
